package com.solution;

/**
 * 4. 寻找两个正序数组的中位数
 * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 * 请你找出并返回这两个正序数组的中位数。
 * 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
 *
 * 示例 1：
 *
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * 示例 2：
 *
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 * 示例 3：
 *
 * 输入：nums1 = [0,0], nums2 = [0,0]
 * 输出：0.00000
 * 示例 4：
 *
 * 输入：nums1 = [], nums2 = [1]
 * 输出：1.00000
 * 示例 5：
 *
 * 输入：nums1 = [2], nums2 = []
 * 输出：2.00000
 *
 * @author liyongkui
 * @date 2020/11/3 13:43
 */
public class Solution0004 {

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length == 0 && nums2.length == 0){
            return 0.0;
        }
        int sIdx1 = 0;
        int sIdx2 = 0;
        int eIdx1 = nums1.length;
        int eIdx2 = nums2.length;
        int mid1 = 0;
        int mid2 = 0;
        for(int i = 0 ; i <= (eIdx1 +eIdx2) / 2 ; i ++){
            mid1 = mid2;
            if(sIdx1 < eIdx1 && (sIdx2 >= eIdx2 || nums1[sIdx1] < nums2[sIdx2])){
                mid2 = nums1[sIdx1++];
            }else{
                mid2 = nums2[sIdx2++];
            }
        }
        if( (eIdx1 +eIdx2) % 2 == 0 ){
            return (mid1 + mid2 )/ 2.0;
        }else {
            return mid2;
        }
    }

    public static void main(String[] args) {
        int[] nums1 = new int[]{1,2,3};
        int[] nums2 = new int[]{2,3,4};
        System.out.println(findMedianSortedArrays(nums1,nums2));
    }

}
